package com.leetcode.math;

public class MySqrt {
    public static void main(String[] args) {
        int x = 1;
        MySqrt mySqrt = new MySqrt();
        System.out.println(mySqrt.mySqrt(1));
    }

    public int mySqrt(int x) {
        if (x == 1) {
            return 1;
        }
        double low = 0.0;
        double high = x * 1.0;
        double mid = (low + high) / 2.0;
        double delta = 0.00001;
        while (Math.abs(mid * mid - x) > delta) {
            if (mid * mid > x) {
                high = mid;
            } else if (mid * mid == x){
                return (int)mid;
            } else {
                low = mid;
            }
            mid = (low + high) / 2.0;
        }
        return (int)mid;
    }

    public int mySqrt2(int x) {
        int low = 0;
        int high = x;
        int ans = -1;
        while (low <= high) {
            int mid = low + (high - low)/2;
            if((long)mid * mid <= x) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }
}
